package sword;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 海琳琦
 * @Date: 2022/5/29 22:14
 * https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/
 */
public class Title35 {

    class Node {
        int val;

        Node next;

        Node random;

        public Node(int val) {
            this.val = val;
        }
    }

    /**
     * 尾插法
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        //旧，新节点
        Map<Node, Node> hash = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            Node temp = new Node(cur.val);
            hash.put(cur, temp);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            Node n = cur.next;
            Node r = cur.random;
            //当前节点next
            hash.get(cur).next = hash.get(n);
            hash.get(cur).random = hash.get(r);
            cur = cur.next;
        }
        return hash.get(head);
    }

    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;
        }
        //在源节点后面copy一个复制节点，先复制值
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }
        //复制random节点
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //分割链表
        Node copyHead = head.next;
        cur = head;
        Node copyCur = copyHead;
        while (cur != null) {
            cur.next = cur.next.next;
            cur = cur.next;
            if (copyCur.next != null) {
                copyCur.next = copyCur.next.next;
                copyCur = copyCur.next;
            }
        }
        return copyHead;
    }




    public static void main(String[] args) {

    }
}
